\documentclass[paper=a4, fontsize=12pt]{scrartcl}
\newcommand{\bfvec}[1]{\mbox{\boldmath$#1$}}
\usepackage{listings}
\usepackage{graphicx} 
\usepackage{charter}
\usepackage{amsmath}
\title{	
\normalfont \normalsize 
\textsc{Shanghai Jiaotong University, Zhiyuan College} \\ [25pt]
\huge Homework 4 \\
}
\author{Feng Shi}
\date{\normalsize\today}
\begin{document}
\maketitle

\begin{enumerate}
	\item[Ex 3.11]
	{\Large Solution:}
	\begin{enumerate}
	\item
	There are $\binom{n}{4}$ ways of choosing a quadruple from a $G(n,\frac{d}{n})$.
	And there are 3 possible squares(4-cycles) in one quadruple.
	So the expected number of squares(4-cycles) in $G(n,\frac{d}{n})$ is
	$$E(4-cycles)=3\binom{n}{4}\bigg(\frac{d}{n}\bigg)^4=
	\frac{d^{4}(n-1)(n-2)(n-3)}{8n^{3}}\approx \frac{d^4}{8}$$
	\item
		$\binom{n}{4}$ for choosing a quadruple and $\bigg(\frac{d}{n}\bigg)^{6}$ for the
	quadruple to be a 4-clique. 
	So the expected number of 4-cliques in $G(n,\frac{d}{n})$ is
	$$E(4-cliques)=\binom{n}{4}\bigg(\frac{d}{n}\bigg)^6=
	\frac{d^6(n-1)(n-2)(n-3)}{24n^5}\approx \frac{d^6}{24n^2}$$
	\end{enumerate}
	\vspace{20pt}
	\item[Problem]
	Search \textit{WWW} for an undirected graph or a data base that can be converted to a graph	  . Find the connected components and count the number of each size.

	{\Large Solution:}

	I downloaded a set of data of facebook users from Stanford Large Network Dataset Collection
	\textbf{(http://snap.stanford.edu/data/egonets-Facebook.html)}
	which provides friend list information about facebook users.

	I counted the connected components with a mathematica function 
\lstset{language=C++}
\lstset{breaklines}
\lstset{extendedchars=false}
\begin{lstlisting}
ConnectedComponents[]
\end{lstlisting}
and got the following result:

\begin{tabular}{|l|r|r|r|r|r|l|} \hline
size of connected components& 3926& 6 &4 &3 &2 &1\\
\hline
number of connected components& 1& 1& 1& 2& 8& 80\\
\hline
\end{tabular}

And the graph (by mathematica) is like:

\begin{center}
    \includegraphics[height=10cm]{facebook}
\end{center}
\end{enumerate}
\end{document}

